프림 알고리즘
"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차
1. 개요
프림 알고리즘은 그래프의 최소 비용 신장 트리를 찾는 데 사용되는 탐욕 알고리즘이다. 그래프의 한 정점에서 시작하여 트리가 모든 정점을 포함할 때까지 최소 가중치를 가진 간선을 선택하여 트리를 확장해 나간다.
알고리즘은 그래프의 각 정점에 연결된 가장 저렴한 비용과 해당 간선을 연결하고, 빈 포레스트에 정점을 추가하는 과정을 반복한다. 시간 복잡도는 사용되는 자료 구조에 따라 다르며, 인접 행렬과 선형 검색을 사용할 경우 O(|V|^2), 이진 힙과 인접 리스트를 사용할 경우 O(|E| log |V|), 피보나치 힙과 인접 리스트를 사용할 경우 O(|E| + |V| log |V|)이다.
프림 알고리즘은 정확성 증명을 통해 신장 트리를 생성하고 최소 비용을 보장함을 알 수 있다. 기본 루프는 순차적이지만, 내부 루프는 병렬화가 가능하다.
더 읽어볼만한 페이지
- 트리 구조 - 덴드로그램
덴드로그램은 데이터 분석에서 데이터 포인트 간 계층적 관계를 시각적으로 표현하는 나무 형태의 다이어그램으로, 군집 분석에서 클러스터 간 유사성을 나타내기 위해 활용되며 다양한 분야에 응용된다. - 트리 구조 - 해시 트리
해시 트리는 데이터 무결성 검증에 사용되는 트리 구조로, 잎 노드는 데이터를, 상위 노드는 자식 노드들의 해시 값을 가지며, 루트 해시를 통해 데이터 손상 여부를 효율적으로 판단할 수 있어 P2P 네트워크, 블록체인 등에서 활용된다. - 에츠허르 데이크스트라 - 교착 상태
교착 상태는 둘 이상의 프로세스가 자원을 점유하고 서로의 자원을 요청하여 더 이상 진행할 수 없는 상태를 의미하며, 상호 배제, 점유 대기, 비선점, 순환 대기 네 가지 조건이 모두 충족되어야 발생하고, 운영 체제는 이를 예방, 회피, 무시, 발견하는 방법으로 관리한다. - 에츠허르 데이크스트라 - 세마포어
세마포어는 데이크스트라가 고안한 정수 변수로, P/V 연산을 통해 자원 접근을 제어하고 동기화 문제를 해결하며, 계수 세마포어와 이진 세마포어로 나뉘어 멀티스레드 환경에서 자원 관리 및 스레드 동기화에 기여한다. - 그래프 알고리즘 - 페이지랭크
페이지랭크는 래리 페이지와 세르게이 브린이 개발한 알고리즘으로, 하이퍼링크로 연결된 문서 집합에서 웹 페이지의 상대적 중요도를 측정하며, 링크를 투표로 간주하여 페이지 순위를 재귀적으로 결정하고, 구글 검색 엔진의 초기 핵심 알고리즘으로 활용되었으며, 다양한 분야에서 활용된다. - 그래프 알고리즘 - 너비 우선 탐색
너비 우선 탐색은 그래프 탐색 알고리즘으로, 큐 자료구조를 사용하여 시작 노드에서 인접한 노드들을 우선적으로 탐색하며, 가중치가 없는 그래프에서 최단 경로를 찾는 데 유용하고 다양한 분야에 활용된다.
| 프림 알고리즘 | |
|---|---|
| 알고리즘 개요 | |
| 종류 | 탐욕 알고리즘 |
| 문제 해결 | 최소 신장 트리 |
| 고안자 | 보이테흐 야르니크 |
| 발표 연도 | 1930년 |
| 재발견 | 로버트 C. 프림 (1957년), 에츠허르 W. 데이크스트라 (1959년) |
| 알고리즘 상세 | |
| 시간 복잡도 (인접 행렬) | O(V^2) |
| 시간 복잡도 (인접 리스트 및 이진 힙) | O((V + E) log V) = O(E log V) |
| 공간 복잡도 | O(V) |
| 다른 이름 | |
| 명칭 | Jarník 알고리즘, Prim-Jarník 알고리즘, Dijkstra 알고리즘 |
2. 역사
2. 1. 보루프카의 초기 발견 (1930년)
2. 2. 프림의 재발견 (1957년)
2. 3. 데이크스트라의 재발표 (1959년)
3. 설명
프림 알고리즘은 그래프의 한 꼭짓점에서 시작하여, 트리가 모든 꼭짓점을 포함할 때까지 그 크기를 확장해 나가는 방식으로 작동한다. 이 알고리즘은 연결된 각 변에 가중치가 주어진 그래프에서 동작한다. 초기화 단계에서는 V' = {x}로 설정하는데, 여기서 x는 V(그래프의 꼭짓점 집합)에 있는 임의의 꼭짓점이다. 또한, E'는 빈 집합 {}으로 초기화된다.
알고리즘은 V' = V가 될 때까지 다음 단계를 반복한다.
- E(그래프의 변 집합)에서 최소 가중치를 갖는 변 (u, v)를 찾는다. 이때 u는 V'에 속해야 하고, v는 V'에 속하지 않아야 한다. 만약 동일한 가중치를 갖는 변이 여러 개 존재할 경우, 임의의 변을 선택한다.
- v를 V'에 추가하고, (u, v)를 E'에 추가한다.
알고리즘이 종료되면, 만들어진 트리 G(V', E')는 최소 비용 신장트리가 된다.
간단히 설명하면, 프림 알고리즘은 다음과 같은 단계를 거친다.
1. 그래프에서 임의로 선택된 단일 정점으로 트리를 초기화한다.
2. 트리를 하나의 에지로 확장한다. 즉, 트리를 아직 트리에 없는 정점에 연결하는 에지 중에서 최소 가중치 에지를 찾아 트리에 추가한다.
3. 모든 정점이 트리에 포함될 때까지 2단계를 반복한다.
이것은 각 단계에서의 최적 선택이 최종적인 최적 해를 보장하는 탐욕(Greedy) 알고리즘의 일종이다.
3. 1. 작동 방식
프림 알고리즘은 그래프에서 임의로 선택된 단일 정점으로 트리를 초기화하고, 트리를 하나의 에지로 확장하는 과정을 반복하여 작동한다. 이 때, 트리를 아직 트리에 없는 정점에 연결하는 에지 중에서 최소 가중치 에지를 찾아 트리에 추가한다. 모든 정점이 트리에 포함될 때까지 이 단계를 반복한다.더 자세하게는, 다음과 같은 의사 코드를 따라 구현할 수 있다.
1. 그래프의 각 정점 ''v''에 대해 숫자 ''C''[''v''](''v''에 연결하는 가장 저렴한 비용)와 에지 ''E''[''v''](해당 가장 저렴한 연결을 제공하는 에지)를 연결한다. 초기에는 모든 ''C''[''v''] 값을 +∞ (또는 최대 에지 가중치보다 큰 숫자)로 설정하고, 각 ''E''[''v'']를 이전 정점에 ''v''를 연결하는 에지가 없음을 나타내는 특별한 플래그 값으로 설정한다.
2. 빈 포레스트 ''F''와 ''F''에 아직 포함되지 않은 정점 집합 ''Q'' (처음에는 모든 정점)를 초기화한다.
3. ''Q''가 비어 있을 때까지 다음 단계를 반복한다.
- a. ''C''[''v'']의 최소값을 갖는 ''Q''에서 정점 ''v''를 찾아 제거한다.
- b. ''F''에 ''v''를 추가하고, ''v''를 다른 정점 ''w''에 연결하는 에지 ''vw''에 대해 루프를 실행한다. ''w''가 아직 ''Q''에 있고 ''vw''의 가중치가 ''C''[''w'']보다 작으면 다음 단계를 수행한다.
- i. ''C''[''w'']를 에지 ''vw''의 비용으로 설정한다.
- ii. ''E''[''w'']를 에지 ''vw''를 가리키도록 설정한다.
4. ''F''를 반환한다. 여기에는 특히 E의 해당 에지가 포함된다.
알고리즘의 시작 정점은 임의로 선택될 수 있다. 알고리즘의 메인 루프의 첫 번째 반복은 ''Q''에 동일한 가중치를 가진 정점 집합을 가지며, 알고리즘은 입력 그래프의 각 연결된 구성 요소의 스패닝 트리를 완료하면 자동으로 ''F''에 새로운 트리를 시작하기 때문이다.
알고리즘은 ''C''[''s'']를 다른 ''C'' 값보다 작은 숫자로 설정하여 특정 정점 ''s''에서 시작하도록 수정할 수 있으며, 관련된 에지가 없는 것으로 표시된 다른 정점을 만날 때마다 중지하여 전체 스패닝 포레스트가 아닌 단일 스패닝 트리를 찾도록 수정할 수 있다.
알고리즘의 다양한 변형은 집합 ''Q''가 연결 리스트 또는 배열 정점, 또는 더 복잡한 우선 순위 큐 자료 구조로 구현되는 방식에서 서로 다르다. 이러한 선택은 알고리즘의 시간 복잡도의 차이로 이어진다. 일반적으로, 우선 순위 큐는 최소 비용을 가진 정점 ''v''를 찾는 데 더 빠르지만, ''C''[''w'']의 값이 변경될 때 더 비싼 업데이트가 필요하다.
3. 2. 의사 코드 (Pseudocode)
프림 알고리즘은 다음과 같이 구현될 수 있다.그래프의 각 정점 ''v''에 대해 숫자 ''C''[''v''](''v''에 연결하는 가장 저렴한 비용)와 에지 ''E''[''v''](해당 가장 저렴한 연결을 제공하는 에지)를 연결한다. 초기화를 위해 모든 ''C''[''v''] 값을 +∞ (또는 최대 에지 가중치보다 큰 숫자)로 설정하고, 각 ''E''[''v'']를 이전 정점에 ''v''를 연결하는 에지가 없음을 나타내는 특별한 플래그 값으로 설정한다.
빈 포레스트 ''F''와 ''F''에 아직 포함되지 않은 정점 집합 ''Q'' (처음에는 모든 정점)를 초기화한다.
''Q''가 비어 있을 때까지 다음 단계를 반복한다.
- ''C''[''v'']의 최소값을 갖는 ''Q''에서 정점 ''v''를 찾아 제거한다.
- ''F''에 ''v''를 추가한다.
- ''v''를 다른 정점 ''w''에 연결하는 에지 ''vw''에 대해 루프를 실행한다. 이러한 각 에지에 대해, ''w''가 아직 ''Q''에 속하고 ''vw''의 가중치가 ''C''[''w'']보다 작으면 다음 단계를 수행한다.
- * ''C''[''w'']를 에지 ''vw''의 비용으로 설정한다.
- * ''E''[''w'']를 에지 ''vw''를 가리키도록 설정한다.
''F''를 반환한다. 여기에는 특히 E의 해당 에지가 포함된다.
위에서 설명한 바와 같이, 알고리즘의 시작 정점은 임의로 선택된다. 알고리즘의 메인 루프의 첫 번째 반복은 ''Q''에 동일한 가중치를 가진 정점 집합을 가지며, 알고리즘은 입력 그래프의 각 연결된 구성 요소의 스패닝 트리를 완료하면 자동으로 ''F''에 새로운 트리를 시작하기 때문이다. 알고리즘은 ''C''[''s'']를 다른 ''C'' 값보다 작은 숫자(예: 0)로 설정하여 특정 정점 ''s''에서 시작하도록 수정할 수 있으며, 관련된 에지가 없는 것으로 표시된 다른 정점을 만날 때마다 중지하여 전체 스패닝 포레스트가 아닌 단일 스패닝 트리를 찾도록 수정할 수 있다(비공식적인 설명과 더 가깝게 일치).
알고리즘의 다양한 변형은 집합 ''Q''가 연결 리스트 또는 배열 정점, 또는 더 복잡한 우선 순위 큐 자료 구조로 구현되는 방식에서 서로 다르다. 이러한 선택은 알고리즘의 시간 복잡도의 차이로 이어진다. 일반적으로, 우선 순위 큐는 최소 비용을 가진 정점 ''v''를 찾는 데 더 빠르지만, ''C''[''w'']의 값이 변경될 때 더 비싼 업데이트가 필요하다.
4. 시간 복잡도
프림 알고리즘의 시간 복잡도는 사용되는 자료 구조에 따라 달라진다.
- 인접 행렬과 선형 검색: 인접 행렬을 사용하고, 최소 가중치 간선을 찾기 위해 배열을 선형 검색하는 경우, 시간 복잡도는 이다. 여기서 는 정점의 개수이다.
- 이진 힙과 인접 리스트: 이진 힙 자료 구조와 인접 리스트 표현을 사용하면, 시간 복잡도를 로 개선할 수 있다. 는 간선의 개수이다.
- 피보나치 힙과 인접 리스트: 피보나치 힙을 사용하면, 시간 복잡도를 로 더욱 낮출 수 있다. 이는 그래프가 밀집되어 가 일 때 특히 효과적이다.
다음 표는 자료 구조에 따른 프림 알고리즘의 시간 복잡도를 요약한 것이다.
| 최소 간선 가중치 데이터 구조 | 시간 복잡도 (총) |
|---|---|
| 인접 행렬, 검색 | O(>V|^2) |
| 이진 힙 및 인접 리스트 | O((>V| + |E|) \log |V|) = O(|E| \log |V|) |
| 피보나치 힙 및 인접 리스트 | O(>E| + |V| \log |V|) |
5. 예제
다음은 프림 알고리즘을 사용하여 최소 비용 신장 트리를 찾는 과정을 단계별로 보여주는 예제이다.
| 그림 | 설명 | 안 보임 | 경계 | 결과 집합 |
|---|---|---|---|---|
 | 왼쪽에 있는 것이 우리가 문제를 풀어야 할 그래프이다. 변 옆에 있는 숫자는 가중치를 나타낸다. 임의의 점을 출발점으로 정할 수 있는데, 꼭짓점 D를 출발점으로 정한다. | C, G | A, B, E, F | D |
 | D와 붙어 있는 꼭짓점 중 A가 가중치 5로 가장 작으므로 꼭짓점 A 및 변 DA를 선택한다. | C, G | B, E, F | A, D |
 | D 혹은 A와 붙어 있는 꼭짓점을 선택해야 하는데, F가 6으로 가장 작으므로, F 및 DF를 선택한다. | C | B, E, G | A, D, F |
 | A에서 7 떨어진 B가 선택된다. DB는 이미 사용되었으므로 이용될 수 없다. | 널 | C, E, G | A, D, F, B |
 | C, E, G 중 E가 가장 가까우므로 E와 EB를 선택한다. 다른 두 변은 이미 사용된 꼭짓점을 포함하므로 선택할 수 없다. | 널 | C, G | A, D, F, B, E |
 | C와 G 중 C가 E에서 5 떨어져 있어 더 가까우므로, C와 EC를 선택한다. | 널 | G | A, D, F, B, E, C |
 | G만 남은 상황에서, E에서 9 떨어진 EG를 선택한다. 모든 꼭짓점이 선택되었고, 최소 비용 신장 트리가 완성되었다. 총 가중치 합은 39이다. | 널 | 널 | A, D, F, B, E, C, G |
6. 정확성 증명
프림 알고리즘의 정확성은 다음 두 가지 명제를 증명함으로써 보일 수 있다.
- 프림 알고리즘으로 얻은 그래프는 신장트리이다.
- 프림 알고리즘으로 얻은 그래프는 최소 비용 신장 트리이다.
신장트리 증명n개의 꼭짓점을 가진 연결된 그래프가 n-1개의 변을 가지면 트리이다. 프림 알고리즘으로 얻은 그래프 P는 n개의 꼭짓점을 연결하고 있고 n-1개의 변을 가지므로 트리이며 모든 점 n개를 가지므로 신장트리이다.
최소 비용 신장 트리 증명 (귀납법 증명)"프림 알고리즘 각 단계에서 얻는 그래프의 간선들을 원소로하는 집합을 포함한 최소비용 신장트리가 항상 존재한다"는 명제를 수학적 귀납법을 통해 증명한다.
# 프림 알고리즘 첫 단계는 간선이 없으므로 간선들의 집합은 공집합이다. 그러므로 최소비용 신장트리가 무엇이든 간선들의 집합을 포함한다.
# 프림 알고리즘의 1부터 n-2 단계까지에서 얻는 그래프의 간선들을 원소로하는 집합을 포함한 최소비용 신장트리가 존재한다고 가정한다.
# n-2 단계로 얻는 그래프는 Q이고 간선들의 집합 L을 포함하는 최소비용 신장트리를 T라고 한다. Q에서 아직 연결되지 않은 마지막 꼭짓점 E를 한점으로 하는 변 e를 그리면 P를 얻는다. 그러므로 P와 T는 L을 공통으로 포함하고 E를 연결하는 변만 차이가 있다. 이때 T는 최소비용 신장트리이고 P도 가중치가 가장 낮은 e를 그려서 얻으므로 T와 P는 비용이 동일하다. 그러므로 n-1 단계에서 얻는 그래프 P의 간선 집합을 포함하는 최소비용 신장트리 P 자신이 존재한다.
''P''를 연결 가중치 그래프라고 하자. 프림 알고리즘의 각 반복에서 하위 그래프의 정점과 하위 그래프 외부에 있는 정점을 연결하는 간선을 찾아야 한다. ''P''가 연결되어 있으므로 모든 정점에 항상 경로가 존재한다. 프림 알고리즘의 출력 ''Y''는 트리인데, 트리 ''Y''에 추가된 간선과 정점이 연결되어 있기 때문이다. 그래프 P의 최소 신장 트리 ''Y1''을 정의하자. 만약 ''Y1''=''Y''이면, ''Y''는 최소 신장 트리이다. 그렇지 않다면, 트리 ''Y1''에 없는 트리 ''Y''를 구성하는 동안 추가된 첫 번째 간선을 ''e''라고 하고, 간선 ''e'' 전에 추가된 간선에 의해 연결된 정점의 집합을 ''V''라고 하자. 그러면 간선 ''e''의 한 끝점은 집합 ''V''에 있고 다른 끝점은 집합 ''V''에 없다. 트리 ''Y1''은 그래프 ''P''의 신장 트리이므로, 두 끝점을 연결하는 트리 ''Y1''에 경로가 존재한다. 경로를 따라 이동하면 집합 ''V''에 있는 정점을 집합 ''V''에 없는 정점에 연결하는 간선 ''f''를 만나게 된다. 간선 ''e''가 트리 ''Y''에 추가된 반복에서 간선 ''f''도 추가될 수 있었고, 가중치가 ''e''보다 작으면 간선 ''e'' 대신 추가되었을 것이며, 간선 ''f''가 추가되지 않았으므로, ''w''(''f'') ≥ ''w''(''e'')임을 알 수 있다.
트리 ''Y2''를 트리 ''Y1''에서 간선 ''f''를 제거하고 간선 ''e''를 추가하여 얻은 그래프라고 하자. 트리 ''Y2''는 연결되어 있고, 트리 ''Y1''과 동일한 수의 간선을 가지며, 간선의 총 가중치는 트리 ''Y1''보다 크지 않으므로, 그래프 ''P''의 최소 신장 트리이며, 간선 ''e''와 집합 ''V''를 구성하는 동안 그 전에 추가된 모든 간선을 포함한다는 것을 쉽게 보여줄 수 있다. 위의 단계를 반복하면 결국 트리 ''Y''와 동일한 그래프 ''P''의 최소 신장 트리를 얻을 것이다. 이는 ''Y''가 최소 신장 트리임을 보여준다.
7. 병렬 알고리즘
프림 알고리즘의 기본 루프는 본질적으로 순차적이어서 병렬 알고리즘으로 병렬화하기 어렵다.[12] 그러나 내부 루프는 사이클을 형성하지 않는 최소 가중치의 다음 간선을 결정하는 과정으로, 사용 가능한 프로세서 간에 정점과 간선을 분할하여 병렬화할 수 있다.[12]
각 프로세서에 길이